package puzzle.projecteuler.p200;



public class Problem113B {

	/**
	 * 对比Problem112
	 * @param args
	 */
	public static void main(String[] args) {
		
		int n = 100;
		long[][] f = f(n);
		long[][] g = g(n);
		long count = 0;
		for (int i = 0; i < n; i ++) {
			for (int j = 1; j < 10; j ++) {
				count += f[i][j] + g[i][j];
			}
			count -= 9;
		}
		System.out.println(count);
	}
	
	/**
	 * 返回长度的数组a[i][j]，第i,j项表示i+1位数中，末尾数是j的increasing-number的数目
	 * @param m
	 * @return
	 */
	public static long[][] f(int m) {
		long[][] a = new long[m][];
		for (int i = 0; i < m; i ++) {
			a[i] = new long[10];
			if (i == 0) {
				for (int j = 0; j < 10; j ++) {
					a[i][j] = 1;
				}
			} else {
				for (int j = 0; j < 10; j ++) {
					a[i][j] = 0;
					for (int k = 0; k <= j; k ++) {
						a[i][j] += a[i-1][k];
					}
				}
			}
		}
		return a;
	}

	/**
	 * 返回长度的数组a[i][j]，第i,j项表示i+1位数中，末尾数是j的decreasing-number的数目
	 * @param m
	 * @return
	 */
	public static long[][] g(int m) {
		long[][] a = new long[m][];
		for (int i = 0; i < m; i ++) {
			a[i] = new long[10];
			if (i == 0) {
				for (int j = 0; j < 10; j ++) {
					a[i][j] = 1;
				}
			} else {
				for (int j = 0; j < 10; j ++) {
					a[i][j] = 0;
					for (int k = j; k <= 9; k ++) {
						a[i][j] += a[i-1][k];
					}
				}
			}
		}
		return a;
	}
}
